'''
归并排序（Merge Sort）是一种分而治之的排序算法。它的基本思想是将一个数组分成两半，对每半部分递归地应用归并排序，
然后将排序好的两部分合并成一个有序的整体。
归并排序的步骤：
分解：将数组分解成两个较小的子数组，直到子数组的大小为1。
递归进行排序并合并：递归地对子数组进行归并排序，并将已排序的子数组合并成一个大的有序数组，直到合并为1个完整的数组。
合并过程：
合并两个已排序的数组是归并排序的核心。具体做法是：
创建一个新的临时数组，用于存放合并后的结果。
使用两个指针，分别指向两个要合并数组的开始位置。
比较两个指针所指向的元素，选择较小的元素放入临时数组中，并将该指针向后移动一位。
重复上述过程，直到某个指针到达数组的末尾。
将另一个数组中剩余的元素（如果有的话）直接复制到临时数组的末尾。
将临时数组的内容复制回原数组，完成合并。
时间复杂度分析
最好情况：O(n log n)
最坏情况：O(n log n)
平均情况：O(n log n)
归并排序的时间复杂度在所有情况下都是O(n log n)，这使得它成为一种非常稳定的排序算法，特别是对于大数据集。归并排序的主要时间消耗在于合并操作，
而合并操作的时间复杂度是线性的，但由于分解过程导致的层数（即递归深度）是log n，因此总体时间复杂度为O(n log n)。
空间复杂度分析
归并排序的空间复杂度主要是用于合并操作的临时数组，以及递归调用栈所占用的空间。
递归调用栈：由于归并排序是递归实现的，其递归深度为log n（假设数组被平均分割），因此递归调用栈的空间复杂度为O(log n)。但在实际应用中，
这个空间通常不是主要的关注点，因为现代操作系统的栈空间通常足够大。
临时数组：在合并过程中，需要一个与原数组大小相同的临时数组来存放合并的结果。因此，归并排序的空间复杂度主要是O(n)。
综合起来，归并排序的空间复杂度是O(n)。
总结
归并排序是稳定排序，是一种高效的排序算法，具有稳定的性能（时间复杂度总是O(n log n)），但其空间复杂度也相对较高（O(n)）。它适用于数据量较大的场景，
尤其是在需要稳定排序的场合。
'''
import random
class Solution:
    def mergeSort(self, arr):
        if len(arr) > 1:
            #找到中间位置分割数组
            mid = len(arr)//2
            left = arr[:mid]
            right = arr[mid:]
            #递归对左右数组归并排序
            self.mergeSort(left)
            self.mergeSort(right)
            #合并左右数组
            i = j = k = 0
            #左右数组都还有数据
            while i < len(left) and j < len(right):
                if left[i] < right[j]:
                    arr[k] = left[i]
                    i += 1
                else:
                    arr[k] = right[j]
                    j += 1
                k += 1
            #左数组还有数据
            while i < len(left):
                arr[k] = left[i]
                i += 1
                k += 1
            #右数组还有数据
            while j < len(right):
                arr[k] = right[j]
                j += 1
                k += 1
        return arr
#示例
if __name__ == '__main__':
    arr = random.sample(range(100), 10)
    print(arr)
    print(Solution().mergeSort(arr))